package leetcode.code787.CheapestFlightsWithinKStops;

/**
 *
 * 算法 决定 数据结构的典型代表
 *
 * @author Max
 * @date 2021年8月24日
 * @description
 */
public class Solution78707 extends CheapestFlightsWithinKStops {

	@Override
	public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
		final int RANGE = 10000 * (k + 1) + 1;
		int min = RANGE;
		int ans[][] = new int[k + 1][n];// ans[次数][目的]
		for (int flytimes = 0; flytimes <= k; flytimes++) {
			for (int to = 0; to < n; to++) {
				ans[flytimes][to] = RANGE;
				if (flytimes == 0) {
					for (int i = 0; i < flights.length; i++) {
						if (flights[i][0] == src) {
							ans[flytimes][flights[i][1]] = flights[i][2];
						}
					}
				}
			}
		}
		min = Math.min(min, ans[0][dst]);
		// 一次一次往目标飞，目标是有效目标，记录
		for (int flytimes = 1; flytimes <= k; flytimes++) {
			for (int[] flight : flights) {
				int from = flight[0];
				int to = flight[1];
				int price = flight[2];
//				if (ans[flytimes - 1][from] != RANGE) {
//					if (ans[flytimes][to] == RANGE) {
//						ans[flytimes][to] = ans[flytimes - 1][from] + price;
//					} else
						ans[flytimes][to] = Math.min(ans[flytimes][to], ans[flytimes - 1][from] + price);
//				}
			}
			min = Math.min(min, ans[flytimes][dst]);
		}
		return min == RANGE ? -1 : min;
	}

	public static void main(String[] args) {
		Solution78707 so = new Solution78707();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();
	}

}
